package myLinkedList;

import pojo.Teacher;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 功能描述: 两个有序链表的合并
 * 2024/05/22
 * <p>
 * ZhangYi
 */
public class TwoSortedLinkedListMerge {
    /**
     * 功能描述: 两个链表之间的合并
     *
     * @param node1 node1
     * @param node2 node2
     * @return {@link Teacher }
     */
    private static Teacher mergeNode(Teacher node1,
                                     Teacher node2) {
        // 任一链表的头结点为空时, 直接返回另一条链表
        if (node1 == null){
            return node2;
        }
        if (node2 == null){
            return node1;
        }

        Teacher head = null;
        Teacher cur = null;
        Teacher next = null;

        head = node1.compare(node1,node2)< 0 ? node1:node2;
        cur = head; //当前节点的指针
        next = head == node1 ? node1.next:node2.next; // 下一节点的指针

        while (next != null){
            cur = cur.compare(cur,next)<0? cur : next; // 获取当前节点和下一节点中较小的节点
            next = cur == cur ? next: cur; // 获取下一节点

            cur = cur.next; // 指针后移
            next = next.next; // 指针后移
        }
        return head;
    }

    /**
     * 功能描述: 合并两个有序链表,借助优先队列PriorityQueue
     *
     * @param node1 node1
     * @param node2 node2
     * @return {@link Teacher }
     */
    public static Teacher merge(Teacher node1,
                                Teacher node2) {
        // 任一链表的头结点为空时, 直接返回另一条链表
        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }

        PriorityQueue priorityQueue = new PriorityQueue<Teacher>(2,new Comparator<Teacher>() {
            @Override
            public int compare(Teacher o1,
                               Teacher o2) {
                return o1.compare(o1,o2);
            }
        });



        while (node1 != null){
            priorityQueue.add(node1);
            node1 = node1.next; // 指针后移
        }
        while (node2 != null){
            priorityQueue.add(node2);
            node2 = node2.next;
        }
        Teacher head = (Teacher)priorityQueue.poll();
        Teacher cur = head; // 当亲节点的指针
        while (!priorityQueue.isEmpty()){
            cur.next = (Teacher)priorityQueue.poll();
            cur = cur.next;
        }
        return head;
    }


    public static void main(String[] args) {
        Teacher node1 = new Teacher(1,"张三");
        node1.next = new Teacher(12,"李四");
        node1.next.next = new Teacher(23,"王五");
        //node1.next.next.next = new Teacher(34,"赵六");
        //node1.next.next.next.next = new Teacher(45,"孙七");

        Teacher node2 = new Teacher(2,"张三");
        node2.next = new Teacher(13,"李四");
        node2.next.next = new Teacher(24,"王五");
        node2.next.next.next = new Teacher(35,"赵六");
        node2.next.next.next.next = new Teacher(46,"孙七");
        Teacher merge = merge(node1,
                              node2);
        Teacher merge2 = mergeNode(node1,node2);
        System.out.println(merge);
    }


}
